这周的内容主要是再介绍了几个Divide and Conquer的例子，最后给出了分析时间复杂度的Master Method。

课程地址：https://www.coursera.org/specializations/algorithms

Course 2 Week 2

The Closest Pair Problem

  • Input:$\mathbb R^2$中$n$个点$P=\{p_1,…,p_n\}$
  • Notation:$d(x_i,x_j)$为欧几里得距离
  • Output:$P$中两个距离最近的点$p,q$

这里我们假设每个点的横坐标，纵坐标均不相同。

这个问题的一维情形可以用排序解决，时间复杂度为$O(n\log n)$，二维情形如果暴力求解，那么时间复杂度为$\theta(n^2)$，现在的目标是把二维情形的时间复杂度降低到$O(n\log n)$。

我们先把这些点按$x$排序为$P_x$，按$y$排序为$P_y$，这一步需要$O(n\log n)$的时间，但这样做显然是不够的，后面还需要Divide+Conquer，伪代码如下：

备注：$Q_x$为$P_x$的前半部分，按$x$轴排序；$Q_y$为$P_x$的后半部分，按$y$轴排序。

这个算法的关键是第5步，如果这个步骤只需要花$O(n)$的时间，那么由上一周的讨论我们知道，这个算法总共需要的时间为$O(n\log n)$，所以现在问题就转换为ClosestSplitPair的问题，这里老师先给出算法：

补充一下，上图中的$S_y$为横坐标$x\in [\overline x - \delta , \overline x +\delta]$的点按照纵坐标$y$排序之后的点集。

这个算法最神奇的地方在于，第二重循环只要执行7次，所以保证了时间复杂度为$O(n)$，下面来解释下这个算法，有如下命题：

令$p\in Q, q\in R$为$d(p,q) < \delta$的split pair，那么

  • (A) $p,q \in S_y$
  • (B) $p,q$在$S_y$中最多距离$7$位

令$p=(x_1,y_1),q=(x_2,y_2)$

命题(A)的证明：

因为$p\in Q, q\in R$，所以$x_1\le \overline x,x_2 \ge \overline x$，而$|x_1-x_2| \le d(p,q) <\delta$，因此$x_1,x_2 \in [\overline x - \delta , \overline x+\delta]$

命题(B)的证明：

先画出以下关键图形：

证明命题（B）需要以下两个引理：

引理1:$S_y$中纵坐标范围介于$p,q$纵坐标之间的点都落在这8个方格之内。

引理2:1个方格内最多有1个点。

引理1的证明：

首先$|y_1-y_2| \le d(p,q) <\delta$，说明满足条件的点的纵坐标落在方格的纵坐标范围内，其次$S_y$中的点横坐标的范围为$ [\overline x - \delta , \overline x+\delta]$，结合以上两点，满足条件的点都落在这8个方格之内。

引理2的证明：

反证法，如果有两个点落在同1个方格内，或者这两个点都属于$Q$，或者都属于$R$，无论那种，这两个点的距离小于等与正方形的对角线的长度$\frac{\sqrt 2 \delta}{2}<\delta$，这与$\delta$的定义相矛盾，所以引理2成立。

命题（B）证明：

如果$d(p, q) < \delta$，那么$p,q$肯定属于上图中的蓝色区域（否则纵坐标之差大于$\delta$），如果$p,q$的下标之差大于$7$，那么$9$个点放入$8$个格子，必然有两个点在同一格子内，这就产生了矛盾。

综上，结合这两个引理可知如果split pair中两点距离小于$\delta$，那么这两个点都属于$S_y$，并且$S_y$中的下标差不会超过7，从而算法是正确的。

Counting Inversions

  • Input: 含有数字$1,2,…,n$任意顺序的数组
  • 逆序数(inversions)的数量，即满足$i<j$​和$a[i]\ge a[j]$的二元组$(i, j)$​的数量

这个问题还是用Divide and Conquer，有如下算法

这个算法最重要的是解决CountSplitInv部分，即计算$i\le \frac n 2 \le j$，但是$a[i]>a[j]$的数量，和之前的算法一样，我们的目标是希望在$O(n)$的时间内解决这个问题，解决之后就可以使得该算法的运行时间为$O(n\log n)$。

但是上述算法可能无法很好地解决该问题，所以这里老师给出一个更强的算法，在计算数量的同时给数组排序，如下：

由B,C推出D的过程为merge，操作和归并排序里一样，以一个具体例子来观察merge操作和逆序数数量的关系

将这个过程总结一下，有如下命题：

split inversions的逆序数量为将第二段数组C中元素$y$复制到D时B中剩余元素的数量之和。

证明：

令$x$为第一段数组B中的元素

1.如果$x$在$y$之前被复制到D，那么$x<y$，说明$(x,y)$不是逆序对。

2.如果$y$在$x$之前被复制到D，那么$y<x$，说明$(x,y)$是逆序对并且$x$之后的数字和$y$都组成逆序对。

因为merge的时间为$O(n)$，所以这个算法的时间为$O(n\log n)$

Matrix Multiplication

如果将每个$n\times n$矩阵拆为$4$个$\frac n2\times \frac n2$，利用Divide and Conquer，有如下算法

这个算法将原问题拆成$8$个子问题，时间复杂度为$\theta(n^3)$，而直接计算的方法也为$\theta(n^3)$，说明这个算法没有提升速度，这时老师介绍了一个神奇的算法：

这个算法的神奇之处为将原问题拆成$7$个子问题，利用主定理，可以计算出时间复杂度小于$\theta(n^3)$。

接下来回顾主定理。

Master Method

我们之前讨论的很多算法的时间复杂度都可以写为如下形式

例如Merge Sort

Karatsuba Multiplication

Master Method描述的就是$T(n) \le aT(\frac n b) + O(n^d)$可以推出怎样的时间复杂度，我们对原条件变形一下

那么同Merge Sort的算法时间推导过程，可以画出如下树状图

那么第$j$层的时间复杂度小于等于

一共的时间复杂度小于等于

现在讨论这个式子，可以看出，这个式子和$a,b^d$的大小关系有关，分三种情况讨论：

(1) $a = b^d$

那么时间复杂度小于等于

从而时间复杂度为

讨论其余两种情况之前，先考虑等比级数

如果$r<1$，那么

如果$r>1$，那么

利用这两个结论继续讨论：

(2) $a>b^d$

此时$\frac{a}{b^d} >1$，由等比级数的性质，我们知道

所以时间复杂度为

(3) $a<b^d$

此时$\frac{a}{b^d} <1$，由等比级数的性质，我们知道

所以时间复杂度为

综合以上三种情形，可以得到Master Method：

如果

那么